package com.leetcode.剑指Offer;

/**
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

 * @author LZF
 *
 */
public class Offer12矩阵中的路径 {
	public boolean exist(char[][] board, String word) {
		for(int i = 0;i < board.length;i++) {
			for(int j = 0;j < board[0].length;j++) {
				if(dfs(board, word, i, j, 0)) return true;
			}
		}
		return false;
    }
	/**
	 * 深搜的规则就是，如果board的当前位置和word的当前位置两个字符相等，则继续深搜board的上下左右四个位置与word的下一个位置想不想等
	 * 注意的点：①三个临界条件
	 * ②访问过的位置要做标记
	 * ③访问完要把标记还回去，不然会影响后面的深搜
	 * @param board
	 * @param word
	 * @param i、j：表示board的当前位置
	 * @param cur：即表示前面深搜完成的有多少个字符，也表示word当前位置
	 * @return true：满足条件
	 */
	public boolean dfs(char[][] board,String word,int i,int j,int cur) {
		//临界条件1：cur表示前面有多少个字符，如果cur已经有了word的全部字符，则返回true
		if(cur == word.length()) return true;
		//临界条件2：i或j越界，都不满足条件
		if(i < 0 || i >= board.length || j < 0 || j >= board[0].length)
			return false;
		//临界条件3：当前位置的字符(board[i][j])与word当前位置的字符不等，则不满足条件
		if(board[i][j] != word.charAt(cur)) return false;
		//当前位置记为'#'，表示已经访问过了,'#'为特殊表示，肯定是与原字符串中的字符是不相等的
		board[i][j] = '#';
		boolean res = dfs(board, word, i + 1, j, cur + 1)//上
				|| dfs(board, word, i - 1, j, cur + 1)//下
				|| dfs(board, word, i, j - 1, cur + 1)//左
				|| dfs(board, word, i, j + 1, cur + 1);//右
		board[i][j] = word.charAt(cur);//把标记还回去，能走到这里，说明原先board[i][j]与word.charAt(cur)是相等的
		return res;
	}
}
